#ifndef RTREE_H
#define RTREE_H

#include "index_manager.h"
#include "../memory/memory_manager.h"
#include <stdint.h>
#include <stdbool.h>
#include <pthread.h>
#include <float.h>

// R-tree configuration
#define RTREE_MAX_CHILDREN 16       // Maximum children per node
#define RTREE_MIN_CHILDREN 4        // Minimum children per node (except root)
#define RTREE_MAX_DIMENSIONS 4      // Maximum spatial dimensions supported
#define RTREE_DEFAULT_DIMENSIONS 2  // Default 2D spatial index

// Coordinate type
typedef double rtree_coord_t;

// Spatial rectangle (MBR - Minimum Bounding Rectangle)
typedef struct rtree_rect {
    rtree_coord_t min[RTREE_MAX_DIMENSIONS]; // Minimum coordinates
    rtree_coord_t max[RTREE_MAX_DIMENSIONS]; // Maximum coordinates
    uint8_t dimensions;                      // Number of dimensions used
} rtree_rect_t;

// Spatial point
typedef struct rtree_point {
    rtree_coord_t coords[RTREE_MAX_DIMENSIONS]; // Coordinates
    uint8_t dimensions;                         // Number of dimensions
} rtree_point_t;

// Forward declarations
typedef struct rtree_node rtree_node_t;
typedef struct rtree_entry rtree_entry_t;
typedef struct rtree_index rtree_index_t;
typedef struct rtree_iterator rtree_iterator_t;

// R-tree entry (spatial key-value pair)
struct rtree_entry {
    rtree_rect_t mbr;          // Minimum bounding rectangle
    void* value;               // Associated value data
    size_t value_size;         // Size of value data
    rtree_node_t* child;       // Child node pointer (for internal nodes)
    uint64_t record_id;        // Record identifier
};

// R-tree node types
typedef enum {
    RTREE_NODE_LEAF = 0,
    RTREE_NODE_INTERNAL
} rtree_node_type_t;

// R-tree node
struct rtree_node {
    rtree_node_type_t type;    // Node type (leaf or internal)
    bool is_root;              // Whether this is the root node
    uint32_t entry_count;      // Number of entries in this node
    uint32_t max_entries;      // Maximum entries this node can hold
    rtree_entry_t* entries;    // Array of entries
    rtree_rect_t mbr;          // Node's minimum bounding rectangle
    
    // Tree structure
    rtree_node_t* parent;      // Parent node
    uint32_t level;            // Level in the tree (0 = leaf level)
    
    // Memory management
    memory_manager_t* memory_mgr;
    
    // Thread safety
    pthread_rwlock_t rwlock;
};

// R-tree iterator state
struct rtree_iterator {
    rtree_index_t* index;      // Parent index
    rtree_node_t* current_node; // Current node
    uint32_t current_entry;    // Current entry index
    bool forward;              // Scan direction
    bool is_valid;             // Iterator validity
    
    // Search criteria
    rtree_rect_t query_rect;   // Query rectangle for spatial queries
    bool use_query_rect;       // Whether to filter by query rectangle
    
    // Stack for tree traversal
    struct {
        rtree_node_t* node;
        uint32_t entry_index;
    } stack[32];               // Traversal stack
    int stack_depth;           // Current stack depth
};

// R-tree index structure
struct rtree_index {
    rtree_node_t* root;        // Root node
    uint32_t max_entries;      // Maximum entries per node
    uint32_t min_entries;      // Minimum entries per node
    uint32_t height;           // Tree height
    uint64_t total_entries;    // Total number of entries
    uint8_t dimensions;        // Number of spatial dimensions
    
    // Configuration
    uint32_t node_size;        // Node size preference
    bool allow_duplicates;     // Whether duplicates are allowed
    
    // Memory management
    memory_manager_t* memory_mgr;
    
    // Thread safety
    pthread_rwlock_t tree_lock;
    
    // Statistics
    uint64_t searches;
    uint64_t inserts;
    uint64_t deletes;
    uint64_t splits;
    uint64_t merges;
    uint64_t spatial_queries;
};

// Spatial query types
typedef enum {
    RTREE_QUERY_INTERSECTS = 0, // Geometries that intersect
    RTREE_QUERY_CONTAINS,       // Geometries that contain the query
    RTREE_QUERY_WITHIN,         // Geometries within the query
    RTREE_QUERY_NEAREST         // Nearest neighbor queries
} rtree_query_type_t;

// Spatial query structure
typedef struct rtree_spatial_query {
    rtree_query_type_t type;   // Query type
    rtree_rect_t rect;         // Query rectangle
    rtree_point_t point;       // Query point (for nearest neighbor)
    uint32_t k;                // Number of nearest neighbors
    double max_distance;       // Maximum search distance
} rtree_spatial_query_t;

// R-tree interface functions
index_interface_t* rtree_interface_create(void);

// R-tree implementation functions
rtree_index_t* rtree_create(memory_manager_t* memory_mgr, uint8_t dimensions);
void rtree_destroy(rtree_index_t* rtree);

// Core operations
index_result_t rtree_insert(rtree_index_t* rtree, const rtree_rect_t* rect,
                           const void* value, size_t value_size);
index_result_t rtree_insert_point(rtree_index_t* rtree, const rtree_point_t* point,
                                 const void* value, size_t value_size);
index_result_t rtree_delete(rtree_index_t* rtree, const rtree_rect_t* rect);
index_result_t rtree_delete_point(rtree_index_t* rtree, const rtree_point_t* point);
index_result_t rtree_search_rect(rtree_index_t* rtree, const rtree_rect_t* rect,
                                index_search_result_t* result);
index_result_t rtree_search_point(rtree_index_t* rtree, const rtree_point_t* point,
                                 index_search_result_t* result);

// Spatial operations
rtree_iterator_t* rtree_spatial_query(rtree_index_t* rtree, 
                                     const rtree_spatial_query_t* query);
rtree_iterator_t* rtree_range_scan_rect(rtree_index_t* rtree,
                                       const rtree_rect_t* rect, bool forward);
rtree_iterator_t* rtree_nearest_neighbors(rtree_index_t* rtree,
                                         const rtree_point_t* point, uint32_t k);

// Iterator operations
bool rtree_iterator_valid(rtree_iterator_t* iter);
index_result_t rtree_iterator_next(rtree_iterator_t* iter);
index_result_t rtree_iterator_current(rtree_iterator_t* iter,
                                     rtree_rect_t* rect, void** value, size_t* value_size);
void rtree_iterator_destroy(rtree_iterator_t* iter);

// Bulk operations
index_result_t rtree_bulk_insert(rtree_index_t* rtree,
                                const rtree_rect_t* rects, 
                                const void** values, size_t* value_sizes,
                                size_t count);
size_t rtree_range_delete_rect(rtree_index_t* rtree, const rtree_rect_t* rect);

// Management operations
index_result_t rtree_clear(rtree_index_t* rtree);
index_result_t rtree_rebuild(rtree_index_t* rtree);
bool rtree_validate(rtree_index_t* rtree);
void rtree_get_stats(rtree_index_t* rtree, index_stats_t* stats);

// Node operations
rtree_node_t* rtree_node_create(memory_manager_t* memory_mgr, rtree_node_type_t type,
                               uint32_t max_entries, uint8_t dimensions);
void rtree_node_destroy(rtree_node_t* node);
index_result_t rtree_node_insert_entry(rtree_node_t* node, rtree_entry_t* entry);
index_result_t rtree_node_delete_entry(rtree_node_t* node, uint32_t pos);
rtree_node_t* rtree_node_split(rtree_node_t* node, rtree_entry_t* new_entry);
index_result_t rtree_node_merge(rtree_node_t* left, rtree_node_t* right);

// Spatial geometry operations
void rtree_rect_init(rtree_rect_t* rect, uint8_t dimensions);
void rtree_rect_from_point(rtree_rect_t* rect, const rtree_point_t* point);
bool rtree_rect_intersects(const rtree_rect_t* rect1, const rtree_rect_t* rect2);
bool rtree_rect_contains(const rtree_rect_t* outer, const rtree_rect_t* inner);
bool rtree_rect_contains_point(const rtree_rect_t* rect, const rtree_point_t* point);
double rtree_rect_area(const rtree_rect_t* rect);
double rtree_rect_margin(const rtree_rect_t* rect);
void rtree_rect_union(rtree_rect_t* result, const rtree_rect_t* rect1, const rtree_rect_t* rect2);
double rtree_rect_distance(const rtree_rect_t* rect1, const rtree_rect_t* rect2);
double rtree_point_distance(const rtree_point_t* point1, const rtree_point_t* point2);

// Point operations
void rtree_point_init(rtree_point_t* point, uint8_t dimensions);
bool rtree_point_equals(const rtree_point_t* point1, const rtree_point_t* point2);

// Node utility functions
void rtree_node_update_mbr(rtree_node_t* node);
rtree_entry_t* rtree_node_choose_leaf(rtree_node_t* node, const rtree_rect_t* rect);
uint32_t rtree_node_choose_split_axis(rtree_node_t* node);
double rtree_node_split_cost(rtree_node_t* node, uint32_t split_index);

// R* tree optimization functions
double rtree_entry_overlap_enlargement(rtree_node_t* node, rtree_entry_t* entry,
                                      const rtree_rect_t* rect);
double rtree_entry_area_enlargement(rtree_entry_t* entry, const rtree_rect_t* rect);
int rtree_choose_subtree(rtree_node_t* node, const rtree_rect_t* rect);

// Utility functions
void rtree_print_tree(rtree_index_t* rtree);
void rtree_print_node(rtree_node_t* node, int level);
void rtree_print_rect(const rtree_rect_t* rect);
void rtree_print_point(const rtree_point_t* point);

// Conversion functions (for index manager interface)
index_result_t rtree_key_to_rect(const void* key, size_t key_size, rtree_rect_t* rect);
index_result_t rtree_key_to_point(const void* key, size_t key_size, rtree_point_t* point);
index_result_t rtree_rect_to_key(const rtree_rect_t* rect, void** key, size_t* key_size,
                                memory_manager_t* memory_mgr);
index_result_t rtree_point_to_key(const rtree_point_t* point, void** key, size_t* key_size,
                                 memory_manager_t* memory_mgr);

#endif // RTREE_H